<HTML><HEAD>
<title>X-Planet</title>
</HEAD>
<BODY>
<center>
<h1>CEOI 2000 Day 1 Problem 1</h1>
<h1>X-Planet</h1>
</center>

All the inhabitants of the
planet X build their houses in a triangular shape. In order to save time 
and effort, they use a special construction method. Everything starts with 
a straight wall. After that, for the construction of every new house they 
just add two new walls to an already existing wall, thus resul-ting in a 
closed, triangular shaped house. Of course, the two new added walls might 
also be used as starting walls for new houses. Sometimes, using this 
con-struc-tion pattern, they arrive at situations where some houses are 
completely enclosed in others (like in the figure). However, this is not a 
problem, because kids might live in the included houses.
<p>
To light up
their houses, the X-habitants install a light bulb on every corner of the 
final construction (a bulb in a corner is common to all the houses sharing 
that corner). On each corner, there is a switch whose touch toggles the 
state (on/off) of the bulb from both that corner and also that of all the 
bulbs of the connected corners. Two corners are considered connected if 
they are placed at the end of the same wall.

<h2>Task</h2>
Write a program that finds a switch touch sequence that will turn on all the 
light bulbs, starting from a given state.

<h2>Input</h2>
File name: <B>X.IN</B><BR>
<B>Line 1</B>: N
<LI>an integer, the number of corners of the building, labelled from 1 to N; <BR>
<B>Lines 2..2x<I>N</I> - 2</B>: I J
<LI>Two integers, separated by a blank, representing a wall between the corners I and J; <BR>
<B>Line 2x<I>N</I> - 1</B>: S<SUB>1</SUB>S<SUB>2</SUB> ... S<SUB>N</SUB> 
<LI>N integers (separated by blanks) whose values are 0's or 1's, corresponding to the state of the N light bulbs; 
<LI>0 means off; 1 means on. <BR><BR>The input data are guaranteed to represent a building that can be constructed in the specified pattern. <BR><BR>

<h2>Output</h2>
File name: <B>X.OUT</B><BR>
<B>Line 1</B>: L<SUB>1</SUB> L<SUB>2</SUB> ... L<SUB>K</SUB> 
<LI>K integers, separated by blanks, represen-ting the list of the labels of the switches to be touched. 
<LI>If there are several solutions, only one is required. 
<LI>If there is no possible solution, you should write in the output file a single line containing the number 0. <BR>

<h2>Limits</h2>
3 &lt;= N &lt;= 1000

<h2>Sample Input</h2>
<PRE>
6                       
1 3
1 4
1 5
2 3
2 4
3 4
3 6
4 5
4 6
0 1 1 1 0 0
</pre>

<h2>Sample Output</h2>
<pre>
1 6
</pre>

<h2>Note</h2>
In the figure below you can see a possible building steps for the example
file; the labels for the bulbs initially illuminated are underlined. 
<CENTER><img src="image/86.gif"></CENTER>
</BODY></HTML>
